package demo2;

import java.util.*;

public class MemoryManager {

    private static final int KB = 1024;

    // 位示图：'0' 表示空闲，'1' 表示占用
    private static final char[] bitmap = new char[64];


    private static int pageLength;
    private static int blockLength;
    private static int blockSize;

    // 缺页次数与置换次数统计
    private static int operationCount = 0;
    private static int fifoPageFaults = 0, lruPageFaults = 0;
    private static int fifoReplacements = 0, lruReplacements = 0;

    // 内存页表
    private static class Memory {
        int[] blockNumber; // 页号 -> 块号
        int[] status;      // 页是否在内存
        int length;

        Memory(int pageLength) {
            blockNumber = new int[pageLength];
            status = new int[pageLength];
            Arrays.fill(blockNumber, -1);
            Arrays.fill(status, 0);
            length = 0;
        }
    }

    // 页访问栈
    private static class Stack {
        int[] stackArray;
        int length;

        Stack(int blockLength) {
            stackArray = new int[blockLength];
            length = 0;
        }
    }

    // FIFO与LRU
    private static Memory fifo, lru;
    private static Stack fifoStack, lruStack;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        System.out.println("输入页长：");
        pageLength = scanner.nextInt();
        System.out.println("输入块长：");
        blockLength = scanner.nextInt();
        System.out.println("输入块大小（KB）：");
        blockSize = scanner.nextInt();

        fifo = new Memory(pageLength);
        lru = new Memory(pageLength);
        fifoStack = new Stack(blockLength);
        lruStack = new Stack(blockLength);

        createBitmap(blockLength);
        printBitmap();

        int[] visitedPages = new int[blockLength];
        int visitedCount = 0;

        while (true) {
            System.out.println("选择操作：\n1. 显示位示图\n2. 进行内存管理");
            int option = scanner.nextInt();

            if (option == 1) {
                printBitmap();
            } else if (option == 2) {
                int logicAddress = inputLogicAddress(scanner);
                int pageNumber = logicAddress / (blockSize * KB);
                int blockNumber = -1;

                boolean alreadyVisited = false;
                for (int i = 0; i < visitedCount; i++) {
                    if (visitedPages[i] == pageNumber) {
                        alreadyVisited = true;
                        break;
                    }
                }

                // 只有当内存未满且未访问时才分配新块
                if (!alreadyVisited && visitedCount < blockLength) {
                    visitedPages[visitedCount++] = pageNumber;
                    blockNumber = findFreeBlock();
                } else {
                    // 内存满或已访问，不再分配新块号，改为复用
                    blockNumber = -1;
                }

                operationCount++;
                runFIFO(blockNumber, pageNumber, logicAddress);
                runLRU(blockNumber, pageNumber, logicAddress);

                printMemoryState();
            } else {
                break;
            }
        }

        scanner.close();
    }

    private static void createBitmap(int freeBlocks) {
        Arrays.fill(bitmap, '1');
        Random rand = new Random();
        for (int i = 0; i < freeBlocks; ) {
            int index = rand.nextInt(64);
            if (bitmap[index] != '0') {
                bitmap[index] = '0';
                i++;
            }
        }
    }

    private static void printBitmap() {
        for (int i = 0; i < bitmap.length; i++) {
            System.out.print(bitmap[i] + "  ");
            if ((i + 1) % 8 == 0) System.out.println();
        }
    }

    private static int inputLogicAddress(Scanner scanner) {
        System.out.println("输入逻辑地址：");
        int address = scanner.nextInt();
        int max = pageLength * blockSize * KB - 1;
        if (address > max) {
            System.out.println("输入非法，最大值为：" + max);
            return inputLogicAddress(scanner);
        }
        return address;
    }

    private static int findFreeBlock() {
        for (int i = 0; i < 64; i++) {
            if (bitmap[i] == '0') {
                bitmap[i] = '1';
                return i;
            }
        }
        return -1;
    }

    private static boolean isHit(int pageNumber, Memory memory) {
        return memory.status[pageNumber] == 1;
    }

    private static void runFIFO(int blockNumber, int pageNumber, int logicAddress) {
        if (!isHit(pageNumber, fifo)) {
            if (fifo.length < blockLength) {
                // 内存未满，直接加载
                fifo.blockNumber[pageNumber] = blockNumber;
                fifo.status[pageNumber] = 1;
                fifoStack.stackArray[fifoStack.length++] = pageNumber;
                fifo.length++;
            } else {
                // 内存满，执行替换
                int replacePage = fifoStack.stackArray[0];
                int reusedBlock = fifo.blockNumber[replacePage];
                fifo.blockNumber[pageNumber] = reusedBlock;
                fifo.status[pageNumber] = 1;
                fifo.blockNumber[replacePage] = -1;
                fifo.status[replacePage] = 0;
                System.arraycopy(fifoStack.stackArray, 1, fifoStack.stackArray, 0, fifoStack.length - 1);
                fifoStack.stackArray[fifoStack.length - 1] = pageNumber;
                fifoReplacements++;
            }
            fifoPageFaults++;
        }

        System.out.println("FIFO 缺页次数：" + fifoPageFaults + " 操作次数：" + operationCount);
        System.out.printf("FIFO 缺页率：%.2f%%  置换率：%.2f%%\n",
                100.0 * fifoPageFaults / operationCount,
                100.0 * fifoReplacements / operationCount);
        printPhysicalAddress(logicAddress, fifo.blockNumber[pageNumber]);
    }

    private static void runLRU(int blockNumber, int pageNumber, int logicAddress) {
        if (!isHit(pageNumber, lru)) {
            if (lru.length < blockLength) {
                lru.blockNumber[pageNumber] = blockNumber;
                lru.status[pageNumber] = 1;
                lruStack.stackArray[lruStack.length++] = pageNumber;
                lru.length++;
            } else {
                int replacePage = lruStack.stackArray[0];
                int reusedBlock = lru.blockNumber[replacePage];
                lru.blockNumber[pageNumber] = reusedBlock;
                lru.status[pageNumber] = 1;
                lru.blockNumber[replacePage] = -1;
                lru.status[replacePage] = 0;
                System.arraycopy(lruStack.stackArray, 1, lruStack.stackArray, 0, lruStack.length - 1);
                lruStack.stackArray[lruStack.length - 1] = pageNumber;
                lruReplacements++;
            }
            lruPageFaults++;
        } else {
            int index = -1;
            for (int i = 0; i < lruStack.length; i++) {
                if (lruStack.stackArray[i] == pageNumber) {
                    index = i;
                    break;
                }
            }
            if (index != -1) {
                System.arraycopy(lruStack.stackArray, index + 1, lruStack.stackArray, index, lruStack.length - index - 1);
                lruStack.stackArray[lruStack.length - 1] = pageNumber;
            }
        }

        System.out.println("LRU 缺页次数：" + lruPageFaults + " 操作次数：" + operationCount);
        System.out.printf("LRU 缺页率：%.2f%%  置换率：%.2f%%\n",
                100.0 * lruPageFaults / operationCount,
                100.0 * lruReplacements / operationCount);
        printPhysicalAddress(logicAddress, lru.blockNumber[pageNumber]);
    }

    private static void printPhysicalAddress(int logicAddress, int blockNumber) {
        int physicalAddress = blockNumber * blockSize * KB + (logicAddress % (blockSize * KB));
        System.out.println("物理地址为（十进制）：" + physicalAddress);
    }

    private static void printMemoryState() {
        System.out.println("------------FIFO---------------LRU--------------");
        for (int i = 0; i < pageLength; i++) {
            System.out.printf("页号 %d 块号 %d 状态位 %d | 页号 %d 块号 %d 状态位 %d\n",
                    i, fifo.blockNumber[i], fifo.status[i],
                    i, lru.blockNumber[i], lru.status[i]);
        }
        System.out.print("FIFO栈: ");
        for (int i = 0; i < fifoStack.length; i++) System.out.print(fifoStack.stackArray[i] + " ");
        System.out.print("\nLRU栈: ");
        for (int i = 0; i < lruStack.length; i++) System.out.print(lruStack.stackArray[i] + " ");
        System.out.println("\n----------------------------------------");
    }
}
